// http://codility.com/cert/start/upsilon2012/

#include <cassert>
#include <vector>

struct tree
{
    unsigned int index;
    int value;

    tree *left;
    tree *right;
    tree *parent;

    tree(unsigned int index, int value, tree *parent = 0, tree *left = 0, tree *right = 0)
        : index(index), value(value), left(left), right(right), parent(parent)
    {
    }

    ~tree()
    {
        if (left) delete left;
        if (right) delete right;
    }

    int depth() const
    {
        return std::max(left ? left->depth() : 0, right ? right->depth() : 0) + 1;
    }

    tree *insert(unsigned int i, int v)
    {
        if (v < value)
        {
            assert(right == 0);
            return right = new tree(i, v, this);
        }

        tree *n = parent, *prev = this;
        while (n && n->value < v)
        {
            assert(n->right == prev);
            prev = n;
            n = n->parent;
        }

        n = new tree(i, v, n, prev);
        prev->parent = n;
        if (n->parent)
        {
            n->parent->right = n;
        }

        return n;
    }

    static tree *create(const std::vector<int> &a)
    {
        if (a.empty())
        {
            return 0;
        }

        tree *current = new tree(0, a.front());
        for (unsigned int i = 1; i < a.size(); ++i)
        {
            current = current->insert(i, a[i]);
        }

        // walk to the root
        while (current->parent)
        {
            current = current->parent;
        }

        return current;
    }

};

int sequence(const std::vector<int> &v)
{
    tree *root = tree::create(v);
    if (!root)
    {
        return 0;
    }

    int val = root->depth();
    delete root;
    return val;
}

using namespace std;
#include <iostream>
#include <ctime>
#include <algorithm>

int main()
{
    {
        int vals[] = {9, 10, 2, -1, 3, -5, 0, -3, 1, 12, 5, 8, -2, 6, 4};
        vector<int> v(vals, vals + sizeof vals / sizeof vals[0]);
        cout << sequence(v) << endl;
    }
    {
        int vals[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        vector<int> v(vals, vals + sizeof vals / sizeof vals[0]);
        cout << sequence(v) << endl;
    }
    {
        int vals[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
        vector<int> v(vals, vals + sizeof vals / sizeof vals[0]);
        cout << sequence(v) << endl;
    }
    
    srand((unsigned int)time(0));
    const unsigned int M = 1000000;
    unsigned int m = 0;
    vector<int> v;
    for (unsigned int cur = 0; cur < 10; cur++)
    {
        unsigned int size = rand() % M;
        v.resize(size);
        for (unsigned int i = 0; i < v.size(); ++i)
        {
            v[i] = i * (rand() % 2 ? -1 : 1);
        }
        random_shuffle(v.begin(), v.end());
        if (v.size() > m)
        {
            cout << "found new max " << v.size() << "; ";
            m = v.size();
        }
        if (cur % 1000 == 0)
        {
            cout << cur << ":" << v.size() << ":" << sequence(v) << endl;
        }
    }
    cout << "max == " << m << endl;
    return 0;
}
